package com.yun.algorithmproblem.leetcode;

import java.util.*;

/*
    30. 串联所有单词的子串
    给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

    s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

        例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
    返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 */
public class Leetcode30 {
    public List<Integer> findSubstring1(String s, String[] words) {
        int count=0;
        int one_word = words[0].length();
        int word_length = words.length;
        int total_length = one_word * words.length;
        HashMap<String, Integer> targetMap = new HashMap<>();
        HashMap<String, Integer> differMap = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for (String word : words) {
            targetMap.compute(word, (k, v) -> {
                if (v == null) {
                    return 1;
                } else {
                    return v + 1;
                }
            });
        }
        for (String word : words) {
            differMap.put(word, 0);
        }
        for (int i = 0; i < one_word; i++) {
            Queue<String> queue = new LinkedList<>();
            for (String word : words) {
                differMap.put(word, 0);
            }
            if (i + total_length > s.length()) {
                break;
            }
            for (int end = i + one_word, start = i; end < s.length()+1; end += one_word) {
                String curr = s.substring(end - one_word, end);
                queue.offer(curr);
                count++;
                System.out.println(count+":"+queue);
                System.out.println("start:"+start);
                System.out.println("end:"+end);
                System.out.println("a:"+differMap.get("a"));
                System.out.println("b:"+differMap.get("b"));
                System.out.println("c:"+differMap.get("c"));
                if (!targetMap.containsKey(curr)) {
                    System.out.println(count+" remove");
                    queue = new LinkedList<>();
                    for (String word : words) {
                        differMap.put(word, 0);
                    }
                    start = end;
                } else {
                    int diff = differMap.get(curr);
                    if (queue.size() == word_length) {
                        System.out.println(count+"----1");
                        System.out.println(diff);
                        System.out.println(targetMap.get(curr));
                        if (diff + 1 > targetMap.get(curr)) {
                            while (queue.peek() != null) {
                                String poll = queue.poll();
                                start+=one_word;
                                System.out.println("start:"+start);
                                if(poll.equals(curr)){
                                    break;
                                }else {
                                    differMap.put(poll,differMap.get(poll)-1);
                                }
                            }
                        }else if(diff+1==targetMap.get(curr)){
                            System.out.println(count+"----2");
                            System.out.println(count+":start:"+start+"------");
                            differMap.put(curr,diff+1);
                            res.add(start);
                            String poll = queue.poll();
                            start+=one_word;
                            differMap.put(poll,differMap.get(poll)-1);
                        }
                    }
                    else {
                        if (diff + 1 > targetMap.get(curr)) {
                            while (queue.peek() != null) {
                                String poll = queue.poll();
                                start+=one_word;
                                System.out.println("start:"+start);
                                if(poll.equals(curr)){
                                    break;
                                }else {
                                    differMap.put(poll,differMap.get(poll)-1);
                                }
                            }
                        }else {
                            differMap.put(curr,diff+1);
                        }
                    }
                }
            }
        }

        return res;
    }

    public List<Integer> findSubstring(String s, String[] words){
        return null;
    }

    public static void main(String[] args) {
        String s = "bcabbcaabbccacacbabccacaababcbb";
        String[] words = {"c","b","a","c","a","a","a","b","c"};
        Leetcode30 test = new Leetcode30();
        List<Integer> substring = test.findSubstring(s, words);
        System.out.println(substring);
    }
}
